﻿// merge_k_linkedlist.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}   
};

struct QueueNode
{
    int val;
    bool operator < (const QueueNode& node) const
    {
        return val > node.val;
    }
};

priority_queue<QueueNode>my_queue;
class Solution {
public:
    static ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto &node : lists)
        {
            ListNode* curr = node;
            while (nullptr != curr)
            {
                QueueNode queue_node = { curr->val };
                my_queue.push(queue_node);
                //cout << "curr: " << curr->val;
                curr = curr->next;
            }
        }
        ListNode* result_head = new ListNode(int());
        ListNode* result_curr = result_head;
        while (!my_queue.empty())
        {
            QueueNode queue_node = my_queue.top();
            my_queue.pop();
            //cout << "queue_node: " << queue_node.val;
            //易错：
            result_curr->next = new ListNode(queue_node.val);
            result_curr = result_curr->next;
        }
        return result_head->next;
    }

    static bool isPalindrome(ListNode* head) {
        vector<int> vec;
        ListNode* curr = head;
        bool result = true;
        while (nullptr != curr)
        {
            vec.push_back(curr->val);
            curr = curr->next;
        }
        for (int i = 0; i < round(vec.size()/2); i++)
        {
            int tail = vec[vec.size() - 1 - i];
            if (tail != vec[i]) result = false;
        }
        return result;

    }

    static bool isPalindrome1(ListNode* head) {
        if (nullptr == head) return true;
        if (nullptr == head->next) return true; //1个节点 true
        if (nullptr != head->next && nullptr == head->next->next) {
            return head->val == head->next->val;//2个节点 判断是否相等
        }

        ListNode* firstEnd = endOfFirstHalf(head);
        ListNode* reverseHead = reverseList(firstEnd->next);
        //cout << "firstEnd: " << firstEnd->val;
        //cout << "reverseHead: " << reverseHead->val;
        bool result = true;
        ListNode* curr1 = head;
        ListNode* curr2 = reverseHead;
        while (nullptr != curr2)
        {
            if (curr1->val != curr2->val)
            {
                result = false;
                break;
            }
            curr1 = curr1->next;
            curr2 = curr2->next;
        }

        firstEnd->next = reverseList(reverseHead);
        return result;
    }


    static ListNode* reverseList(ListNode* head) {
        ListNode* curr = head;
        ListNode* prev = nullptr;
        while (nullptr != curr)
        {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        //易错！
        return prev;
    }

    static ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (nullptr != fast->next && nullptr != fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    //Solution
};

ListNode* CreateList(vector<int>vec)
{
    ListNode* head = new ListNode(vec[0]);
    ListNode* curr = head;
    for (int i = 1; i < vec.size(); i++)
    {
        curr->next = new ListNode(vec[i]);
        curr = curr->next;
    }
    return head;
}

void CheckList(ListNode* node)
{
    ListNode* curr = node;
    while (nullptr != curr)
    {
        cout << curr->val;
        curr = curr->next;
    }
}

int main()
{
    //[-1,-1,-1],[-2,-2,-1]
    /*vector<int> vec1 = { -1,-1,-1 };
    vector<int> vec2 = { -2,-2,-1 };
    ListNode* head1 = CreateList(vec1);
    ListNode* head2 = CreateList(vec2);

    vector<ListNode*> lists = { head1, head2 };
    ListNode* result = Solution::mergeKLists(lists);

    CheckList(result);*/

    vector<int> vec1 = { 1,2,1 };
    ListNode* head1 = CreateList(vec1);
    //ListNode* revese1 = Solution::reverseList(head1);
    //CheckList(revese1);
    bool result = Solution::isPalindrome1(head1);
    cout << result << endl;

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
